
fn main() {
    println!("Hello, coin_change!");
    let coins:[i32; 3] = [1,2,5];
    let amount = 11;
    println!("{}", coin_change_1(&coins, &amount));
}

//穷举实现
fn coin_change_1(coins:&[i32], amount:&i32)->i32
{
    if 0 == *amount{
        return 0;
    }
    if 0 > *amount{
        return -1;
    }

    let mut res:i32 = i32::MAX;

    for coin in coins{
       let subproblem = coin_change_1(coins, &(*amount - *coin));
       if -1 == subproblem{
           continue;
       }
       if res > subproblem+1{
           res = subproblem + 1;
       }
    }
    return  res;
}